package leetcode.weekly.week307;

//Solution2Test
public class Solution2 {

	public String largestPalindromic(String num) {
		int[] nums = new int[10];
		char[] cs = num.toCharArray();
		for (int i = 0; i < cs.length; i++) {
			int cur = cs[i] - '0';
			nums[cur]++;
		}
		StringBuffer pre = new StringBuffer();
		for (int i = 9; i >= 0; i--) {
			if (nums[i] != 0) {
				if (i != 0 || (i == 0 && pre.length() != 0)) {
					if (nums[i] > 1) {
						int half = nums[i] >> 1;
						for (int j = 0; j < half; j++) {
							pre.append(i);
						}
						nums[i] -= half << 1;
					}
				}
			}
		}
		int mid = -1;
		for (int i = 9; i >= 0 && mid == -1; i--) {
			if (nums[i] != 0) {
				mid = i;
			}
		}
		StringBuffer ans = new StringBuffer();
		if (pre.length() != 0) {
			ans.append(pre);
		}
		if (mid != -1) {
			ans.append(mid);
		}
		if (pre.length() != 0) {
			ans.append(pre.reverse());
		}
		return ans.toString();
	}

}
